package day325;

import common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author tmh
 * @date 2023/3/25 17:37
 * @description 二叉搜索树的中序遍历的结果是有序的
 */
public class T98 {
    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        //往左面遍历
        if (!isValidBST(root.left)) {
            return false;
        }
        //处理逻辑
        //比较当前的值与pre，如果当前节点的值比pre小，就说明不满足二叉搜索树的条件
        if (root.val < pre) {
            return false;
        }
        //更新pre的值
        pre = root.val;
        //最后再往右面进行遍历
        return isValidBST(root.right);
    }

    /**
     * 中序遍历的迭代写法
     * 1.先把根节点以及左节点全部放在栈里面
     * 2.之后再pop的每个节点我们对它进行逻辑处理
     * 3.之后再往右子树方向走
     *
     * @param root
     * @return
     */
    public boolean isValidBST2(TreeNode root) {
        //用栈来维护实现,这里就相当于是处理左的逻辑了
        Deque<TreeNode> stack = new LinkedList<>();
        long pre = Long.MIN_VALUE;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            //这里就是处理的是中的逻辑
            if (root.val <= pre) {
                return false;
            }
            pre = root.val;

            //这里就是右的逻辑
            root = root.right;
        }
        return true;
    }
}




